五大经典算法

您所在的位置:网站首页 快速查找 算法的优缺点有哪些 五大经典算法

五大经典算法

2024-07-10 04:12| 来源: 网络整理| 查看: 265

前言

我们都知道在常用的五大常用的经典算法:分治算法、贪心算法、动态规划算法、回溯算法、分支界限算法、每个算法在计算机科学中都有很重要的地位;本篇文章会介绍这其中分治算法一种实现 ,包括顺序查找、二分查找、快速排序  、归并排序等方法

定义

分治法的从字面意思来看“分而治之”,就是将一个复杂问题分成两个或者多个相同或相似的子问题,在把子问题分成更小的问题。。。。直到最后子问题可以简单的求解,即子问题的答案就是原问题的答案。各位这样一看看,是不是觉得突然想起某个算法,对,就是递归,或者也许你想起的是归并排序算法,或者二分查找法也好,也并不重要。这个思想就是这些算法的基础,然后我们从小及大来理解这个算法吧

顺序查找

如果线性表为无序表,即表中元素的排列是无序的,则不管线性表采用顺序存储还是链式存储,都必须使用顺序查找。如果线性表有序,则采用链式存储结构,则也必须使用顺序查找的方式

这种方式在我们的代码开发种算是最常用的查找方法;例如在LinkedList(链表结构)查找 某个值。 当然在树结构是采用这种方式。下图就是顺序查找的在二叉排序树上的一种体现 二分查找法

前提条件:数据已经排序才能进行二分查找法  数组顺序存储结构

通过上图进行分析到我们二分查找法 查找速率是相当快的,在顺序数组中查找方法,并且时间复杂度只有O(logn) ,也就是说如果你有8个元素,只需要三次就可以查找到;这也是将问题拆分开,问题最小化。

正确的写一个二分查找是比较难的,需要设计成左闭右开结构,是一种区间无重复的思想; random(0,1)等大量的数学函数 for(int i=0;i



【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3